package com.lwl.Algorithmic_data_structure.动态规划;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class robotWalk {
    @Test
    public void test(){
        System.out.println(ways(7, 1, 5, 10));
        System.out.println(ways2(7, 1, 5, 10));
        System.out.println(ways(7, 2, 4, 4));
        System.out.println(ways2(7, 2, 4, 4));
        System.out.println(ways(7, 2, 4, 20));
        System.out.println(ways2(7, 2, 4, 20));
    }
    public int ways(int N, int start, int aim, int K) {
        int[] dp = new int[N];
        List<Integer> path = new ArrayList<>();
        path.add(start);
        return process(N,start,aim,K,path);
    }
    // 1 ~ N (没有0下标)
    private int process(int n, int cur, int aim, int steps, List<Integer> path) {
        if (steps == 0 && cur == aim){
//            for (int i = 0; i < path.size(); i++) {
//                System.out.print(path.get(i) + " ");
//            }
//            System.out.println();
            return 1;
        }
        if (steps == 0){
            return 0;
        }
        int p1 = 0,p2 = 0;
        if (cur != 1){
            path.add(cur-1);
            p1 = process(n,cur - 1,aim,steps - 1, path);
            path.remove(path.size()-1);
        }
        if (cur != n){
            path.add(cur+1);
            p2 = process(n,cur + 1,aim,steps - 1, path);
            path.remove(path.size()-1);
        }
        return  p1+p2;
    }
    public int ways2(int N, int start, int aim, int K) {
        int[][] member = new int[N+1][K+1];
        for (int i = 0; i <= N; i++) {
            Arrays.fill(member[i],-1);
        }
        int res = process2(N,start,aim,K,member);
        for (int i = 0; i < member.length; i++) {
            for (int j = 0; j < member[i].length; j++) {
                System.out.print(member[i][j] + " ");
            }
            System.out.println();
        }
        return res;
    }
    // 1 ~ N (没有0下标)
    private int process2(int n, int cur, int aim, int steps,int[][] member) {
        if (steps == 0 && cur == aim){
            return 1;
        }
        if (steps == 0){
            return 0;
        }
        if (member[cur][steps] != -1){
            return member[cur][steps];
        }
        int p1 = 0,p2 = 0;
        if (cur != 1){
            p1 = process2(n,cur - 1,aim,steps - 1, member);
        }
        if (cur != n){
            p2 = process2(n,cur + 1,aim,steps - 1, member);
        }
        member[cur][steps] = p1 + p2;
        return  p1 + p2;
    }
}
